/*
 * Cette class contient la méthode de la
 * Recherche Tabou
 */

package Algorithmes;

import Modele.Solution;
import Modele.Voisin;
import Modele.ListeInterdite;
/**
 *
 * @author Rodrigo and Khai Minh
 */
public class MetaHeuristiques {

    Solution solution,
	meilleureSolution,
	meilleurVoisin;
    long     tempsAttenteMaximum;

    /*
     * Contruit une instance de MetaHeuristique avec une solution initiale
     */
    public MetaHeuristiques(Solution initiale, long attente)
    {
        this.solution		     = initiale;
	    this.meilleureSolution   = initiale;
        this.tempsAttenteMaximum = attente;
    }

    public void genererVoisinage(Cycle modele)
    {
        long tempsDebut = System.currentTimeMillis(); // Prend l'heure actuelle
        long tempsFin   = tempsDebut;
        //this.timeBest = tempsDebut;

        ListeInterdite listeInterdite = new ListeInterdite(modele.getGraphe().getNbrSommets());
        // Tant qui le temps maximum d'attente n'a pas ete atteint
        while ((tempsFin - tempsDebut) < this.tempsAttenteMaximum)
        {
	    this.meilleurVoisin = null;

            // Pour chaque ville du graph, genere deux voisin en suivant les
            // criteres suivantes:
            // - Soit on enleve la ville courante du cycle
            // - Soit on ajoute la ville courante au cycle

            int SommetChange = -1;

            for(int ville = 0; ville < this.solution.getNombreVilles();
                ville++)
            {
				// Creation du nouveau voisin qui est une copie de la courante
                Solution nouvelleSolution = this.solution.cloner();
				int diffCoutCycle       = 0;
				int diffCoutAssignement = 0;

				// Si la ville est dans le cycle
				if(this.solution.getPosMatrice(ville, ville) == 1)
				{
					// Generer une solution sans la ville dans le cycle

					Voisin voisins = new Voisin();

					// La ville courant n'est pas dans le cycle
					nouvelleSolution.setPosMatrice(ville, ville, 0);

					// Cherche les voisins de la ville dans le cycle
					voisins = this.getVoisinsVille(ville);

					// Enleve l'arc entre la ville et son precedent
					nouvelleSolution.setPosMatrice(voisins.getPrecedent(), ville, 0);
					nouvelleSolution.setPosMatrice(ville, voisins.getPrecedent(), 0);
					diffCoutCycle = -(modele.getGraphe().getCycleDistance(ville, voisins.getPrecedent()));

					// Si il y a plus de 2 villes dans le cycle, il faut enlever
					// aussi l'arc entre la ville et la suivant et ajouter un
					// arc entre la precedente et la suivante
					if(voisins.getPrecedent() != voisins.getSuivant())
					{
						// Enleve l'arc entre la ville et la suivante
						nouvelleSolution.setPosMatrice(ville, voisins.getSuivant(), 0);
						nouvelleSolution.setPosMatrice(voisins.getSuivant(), ville, 0);
						diffCoutCycle += -(modele.getGraphe().getCycleDistance(ville, voisins.getSuivant()));

						// Ajoute l'arc entre les voisins de la ville enleve'
						nouvelleSolution.setPosMatrice(voisins.getPrecedent(), voisins.getSuivant(), 1);
						nouvelleSolution.setPosMatrice(voisins.getSuivant(), voisins.getPrecedent(), 1);
						diffCoutCycle += modele.getGraphe().getCycleDistance(voisins.getPrecedent(), voisins.getSuivant());
					}

					// Met a jour les arc d'assignement qui etaient liee a la
					// ville enleve' du cycle
					for(int voisin = 0; voisin < this.solution.getNombreVilles(); voisin++)
					{
						// S'il y a un arc d'assignement de 'voisin' vers 'ville'
						if(this.solution.getPosMatrice(voisin, ville) == 2)
						{
							int	  villeAux = nouvelleSolution.getPremiereVilleCycle();
							float coutMin  = modele.getGraphe().getCoutAssignement(voisin, villeAux);

							// Suprime l'arc d'asignement voisin-ville
							nouvelleSolution.setPosMatrice(voisin, ville, 0);
							nouvelleSolution.setPosMatrice(ville, voisin, 0);
							diffCoutAssignement -= modele.getGraphe().getCoutAssignement(voisin, ville);

							// Fait une suposition pour le nouveau assignement
							nouvelleSolution.setPosMatrice(voisin, villeAux,  2);
							nouvelleSolution.setPosMatrice(villeAux, voisin, -2);
							diffCoutAssignement += modele.getGraphe().getCoutAssignement(voisin, villeAux);

							// Cherche la ville du cycle dont le cout entre le
							// voisin et elle est minimum
							for(int villeCycle = 0; villeCycle < this.solution.getNombreVilles(); villeCycle++)
							{
								// Si la ville est dans le cycle
								if(nouvelleSolution.getPosMatrice(villeCycle, villeCycle) == 1)
								{
									// S'il a trouve' un meilleur cout d'assignement
									if(modele.getGraphe().getCoutAssignement(voisin, villeCycle) < coutMin)
									{
										// Suprime l'arc qui avait le meilleur cout
										nouvelleSolution.setPosMatrice(voisin, villeAux, 0);
										nouvelleSolution.setPosMatrice(villeAux, voisin, 0);
										diffCoutAssignement -= modele.getGraphe().getCoutAssignement(voisin, villeAux);

										// Met a jour la ville du nouveau arc d'assignement
										villeAux = villeCycle;
										coutMin  = modele.getGraphe().getCoutAssignement(voisin, villeAux);

										nouvelleSolution.setPosMatrice(voisin, villeAux,  2);
										nouvelleSolution.setPosMatrice(villeAux, voisin, -2);
										diffCoutAssignement += modele.getGraphe().getCoutAssignement(voisin, villeAux);
									}
								}
							}
						}
					} // Mise a jour de l'arc d'assignement

					// Met a jour les couts de cycle et d'assignement de la
					// nouvelle solution
					nouvelleSolution.setCoutTotalCycle(this.solution.getCoutTotalCycle() + diffCoutCycle);
					nouvelleSolution.setCoutTotalAssignement(this.solution.getCoutTotalAssignement() + diffCoutAssignement);

					// TODO: Verifie si la nouvelle solution est dans la liste d'interdits
                    if (listeInterdite.estDansListeNonSupprimer(ville)){
                        nouvelleSolution = null;
                    }
                }
				else // Si la ville n'est pas dans le cycle
				{
					// Generer une solution en mettant la ville dans le cycle

					diffCoutAssignement = -modele.Dec(ville, nouvelleSolution);
					diffCoutCycle       =  modele.Inc(ville, nouvelleSolution);

					nouvelleSolution.setCoutTotalCycle(this.solution.getCoutTotalCycle() + diffCoutCycle);
					nouvelleSolution.setCoutTotalAssignement(this.solution.getCoutTotalAssignement() + diffCoutAssignement);

					// TODO: Verifie si la nouvelle solution est dans la liste d'interdits
                    if (listeInterdite.estDansListeNonAjouter(ville)){
                        nouvelleSolution = null;
                    }
				}

				// Mettre a jour le meilleur voisin jusqu'au moment
				// Si c'est le premier voisin trouve'
				if(this.meilleurVoisin == null)
				{
					this.meilleurVoisin = nouvelleSolution;
                    SommetChange = ville;
				}
				else // Si ce n'est pas le premier, verifie s'il est meilleur
				{
					// Si la nouvelle solution a un cout total meilleur
					if(nouvelleSolution.getCoutTotal() < this.meilleurVoisin.getCoutTotal()){
						this.meilleurVoisin = nouvelleSolution;
                        SommetChange = ville;
                    }
				}
            }

			// TODO: Une fois qu'il a trouve' un meilleur voisin, met le dans la liste
			// d'interdits

            listeInterdite.miseAJour();
            if (this.meilleurVoisin != null)
                if (this.meilleurVoisin.getPosMatrice(SommetChange, SommetChange) == 1) // On vient d'ajouter dans le cycle
                    listeInterdite.interdireSupprimer(SommetChange);
                else  // On vient de supprimer ce sommet du cycle
                    listeInterdite.interdireAjouter(SommetChange);

            // Accepte la nouvelle solution, meme si elle a un cout superieur
			this.solution = this.meilleurVoisin;

			// Si on a trouve' une meilleure solution
			if(this.solution.getCoutTotal() < this.meilleureSolution.getCoutTotal())
			{
				this.meilleureSolution = this.solution;
			}

			tempsFin = System.currentTimeMillis();
        } // Tant que le temps d'attente maximum n'a pas ete atteint
    }

	// Cherche les deux voisins de la ville dans le cycle
	public Voisin getVoisinsVille(int villeReference)
	{
		Voisin result = new Voisin();

		for (int voisin = 0; voisin < this.solution.getNombreVilles(); voisin++)
		{
			// Si il existe un arc entre la ville et le voisin
			if (this.solution.getPosMatrice(villeReference, voisin) == 2)
			{
				if (result.getPrecedent() == -1)
					result.setPrecedent(voisin);
				else
					result.setSuivant(voisin);
			}
		}

		return result;
	}

    public void setSolution(Solution nouvelle)
    {
        this.solution = nouvelle;
    }

	public Solution getSolution()
    {
        return this.solution;
    }

    public Solution getMeilleureSolution()
    {
        return this.meilleureSolution;
    }
}
